package mapandset;

import java.util.*;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Test {
    public static TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }

        TreeNode root = pRootOfTree;
        while(root.left != null) {
            root = root.left;
        }

        //递归
        creatList(pRootOfTree);
        return root;
    }

    private static TreeNode creatList(TreeNode root){
        if(root == null) {
            return null;
        }

        TreeNode leftNode = creatList(root.left);

        root.left = leftNode;
        if(leftNode != null) {
            leftNode.right = root;
        }

        TreeNode rightNode = creatList(root.right);
        if(rightNode != null) {
            rightNode.left = root;
        }

        return null;
    }
    public static void main1(String[] args) {
        TreeNode root = new TreeNode(10);
        TreeNode root1 = new TreeNode(6);
        TreeNode root2 = new TreeNode(4);
        TreeNode root3 = new TreeNode(8);
        TreeNode root4 = new TreeNode(14);
        TreeNode root5 = new TreeNode(12);
        TreeNode root6 = new TreeNode(16);

        root.left = root1;
        root.right = root4;
        root1.left = root2;
        root1.right = root3;
        root4.left = root5;
        root4.right = root6;

        TreeNode list = Convert(root);

        System.out.println(list);

    }
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++) {
            if(map.containsKey(nums[i])) {
                int j = map.get(nums[i]);
                if(Math.abs(j - i) <= k) {
                    return true;
                }
            } else {
                map.put(nums[i],i);
            }
        }
        return false;
    }

    public static List<String> topKFrequent(String[] words, int k) {
        int count = 0;
        TreeMap<String,Integer> map = new TreeMap<>();
        for(int i=0;i<words.length;i++) {
            String str = words[i];
            if(map.containsKey(str)) {
                count = map.get(str) + 1;
                map.put(str,count);
            } else {
                map.put(str,1);
            }
        }

        PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){
            public int compare(Map.Entry<String,Integer> o1, Map.Entry<String,Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o1.getKey().compareTo(o2.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //创建小根堆
        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            queue.offer(entry);
            if(queue.size() > k) {
                queue.poll();
            }
        }

        List<String> list = new ArrayList<>();
        while(!queue.isEmpty()) {
            list.add(queue.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        String[] arr = {"i","love","leetcode","i","love","coding"};
        List<String> list = topKFrequent(arr,2);
        System.out.println(list);
    }

    public static void main2(String[] args) {
        int[] arr = {1,0,1,1};
        containsNearbyDuplicate(arr,1);

    }
}
